Creating a Layer 2 Virtual Private Network (L2VPN) over an Ethernet network is a problem service providers have had for some time. There are a number of solutions that exist or are in the process of being developed, but a number of issues are associated with these solutions. One issue is a slow recovery or convergence time in the event of failure, such as a physical link failure. For example, many solutions create L2VPNs by assigning customers to separate VLANs or service instances as defined in the IEEE 802.1Q, IEEE 802.1ad, or IEEE 802.1ah standards. These solutions rely on a Spanning Tree Protocol (STP) to restore traffic for bridged networks when physical links fail. However, it may take seconds to restore traffic after a link fails when STP is used in common service provider networks. This is not acceptable for service provides that need to provide Carrier Ethernet services with traffic restoration requirements on the order of tens of milliseconds. A typical desired network restoration time is less than 50 ms, which cannot be realistically achieved using STP. Another issue faced by service providers is lack of control over and/or knowledge of the paths or routes between nodes in a L2VPN. For example, one solution called Virtual Private LAN Services (VPLS) operates over Multi Protocol Label Switching (MPLS). The MPLS protocol sets up all routes, but as a result, the service provider does not have complete control over provisioned routes or how new routes will be dynamically chosen after link or node failures. Many service providers come from a telecommunications background where they had full control over and knowledge of routes, as well as backup routes, and may prefer having this knowledge and control. It would be desirable to develop new techniques for creating a L2VPN over an Ethernet network that address these issues.